/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 20404
 * Date: 2023-01-26
 * Time: 22:44
 */




class ListNode {
      int val;
      ListNode next;
      ListNode() {

      }
    ListNode(int val) {
       this.val = val;
    }
    ListNode(int val, ListNode next) {
       this.val = val; this.next = next;
    }


 }



public class Test {

    //逆序
    public ListNode reverseList(ListNode head) {
        if(head == null) {
            return null;
        }
        ListNode cur = head.next;
        head.next = null;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }
//快慢指针  --》 找中间
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast .next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

//快慢指针 --》 步数差
public ListNode FindKthToTail(ListNode head,int k) {
    if(head == null || k <= 0) {
        return null;
    }
    ListNode fast = head;
    ListNode slow = head;
    while(--k != 0) {
        fast = fast.next;
        if(fast == null) {
            return null;
        }
    }
    while(fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

//谁小（大）谁先排的思想  合并有序表
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode head = null;
    ListNode cur1 = list1;
    ListNode cur2 = list2;
    if(list1 == null) {
        return list2;
    }
    if(list2 == null) {
        return list1;
    }
    if(list2.val <= list1.val) {
        head = cur2;
        cur2 = cur2.next;
    }else {
        head = cur1;
        cur1 = cur1.next;
    }
    ListNode cur = head;
    while(cur1 != null && cur2 != null) {
        if(cur1.val <= cur2.val) {
            cur.next = cur1;
            cur = cur.next;
            cur1 = cur1.next;
        }else {
            cur.next = cur2;
            cur = cur.next;
            cur2 = cur2.next;
        }
    }
    if(cur1 != null) {
        cur.next = cur1;
    }
    if(cur2 != null) {
        cur.next = cur2;
    }
    return head;
}

//编写一段代码将所有小于x的结点排在其余结点之前
public ListNode partition(ListNode pHead, int x) {
    if (pHead == null) {
        return null;
    }
    ListNode fast = pHead.next;
    ListNode prev = pHead;
    ListNode slow = null;
    ListNode cur = null;
    while (fast != null) {

        if (fast.val < x) {
            if (slow == null) {
                slow = fast;
                cur = slow;
            } else {
                cur.next = fast;
                cur = cur.next;
            }
        } else {
            prev.next = fast;
            prev = fast;
        }
        fast = fast.next;
    }
    prev.next = fast;
    if (pHead.val < x) {
        ListNode tmp = pHead;
        pHead = pHead.next;
        tmp.next = slow;
        slow = tmp;
    }
    if (slow == null) {
        slow = pHead;
    } else {
        cur.next = pHead;
    }
    return slow;
}

//链表回文，此法空间大
public boolean chkPalindrome1(ListNode A) {

    if(A == null) {
        return false;
    }
    ListNode head = A;
    ListNode B = A;
    while(A != null) {
        ListNode C = new ListNode(A.val);
        C.next = B;
        B = C;
        A = A.next;
    }
    while(head != null) {
        if(head.val != B.val) {
            return false;
        }
        head = head.next;
        B = B.next;
    }
    return true;

}
//链表回文，逆序一半表

    public boolean chkPalindrome2(ListNode listNode) {
        ListNode fast = listNode;
        ListNode slow = listNode;

        if(fast == null) {
            return false;
        }

        //找到中间，千万小心数据丢失！！！
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //逆序后面的表
        ListNode cur = slow.next;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

        //前后指针相对走(fast位置不一定，所以用slow)
        while(listNode != slow) {
            if(listNode.val != slow.val) {
                return false;
            }
            //偶数的时候！！！会出现右边（我们逆序的）会回去，所以就会错过，从而空指针异常，并且结果错误
            if(listNode.next != slow) {
                return true; //这里要在下一次走动之前（错位）判断，并且要在判断值是否相同之后！，这个就是中间的那连个值（相邻）
            }

            //走动
            listNode = listNode.next;
            slow = slow.next;
        }
        return true;
    }
//相交链表
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode curA = headA;
    ListNode curB = headB;
    int countA = 0;
    int countB = 0;
    while(curA != null && curB != null) {
        curA = curA.next;
        curB = curB.next;
    }
    while(curA != null) {
        headA = headA.next;
        curA = curA.next;
    }
    while(curB != null) {
        headB = headB.next;
        curB = curB.next;
    }
    while(true) {
        if(headA == headB) {
            return headA;
        }
        headA = headA.next;
        headB = headB.next;
    }
}
    public static void main(String[] args) {

    }
}
